home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c++-part1 / 9457 < prev    next >
Encoding:
Text File  |  1996-08-05  |  1.7 KB  |  81 lines
  1. Path: news.nevada.edu!not-for-mail
  2. From: kesslert@nevada.edu (Troy Kessler)
  3. Newsgroups: comp.lang.c++
  4. Subject: Here Is The Fastest Sort Just Change Integers To Reals
  5. Date: 1 Mar 1996 17:09:06 GMT
  6. Organization: University of Nevada System Computing Services
  7. Message-ID: <4h7avi$o0d@news.nevada.edu>
  8. NNTP-Posting-Host: unauthenticated_user@pioneer.nevada.edu
  9. X-Newsreader: TIN [UNIX 1.3 950520BETA PL0]
  10.  
  11. #include <fstream.h>
  12. void Quicksort(int [],int loBound,int hiBound );
  13. int main()
  14. {
  15. ifstream inFile;               //needed to use input file
  16. ofstream outFile;                 //needed to use output file
  17. inFile.open("int.dat");    //open int.dat which contains input
  18. outFile.open("outfile.dat");      //open outfile.dat gets output
  19. int number;
  20. inFile>>number;
  21. int i;
  22. int vec[200];
  23. int loBound=0;
  24. int hiBound=number;
  25. for(i=loBound;i<hiBound;i++)
  26. {
  27. inFile>>vec[i];
  28. }
  29.  
  30. Quicksort(vec,loBound,hiBound);
  31. outFile<<number<<endl;
  32. for(i=loBound+1;i<hiBound+1;i++)
  33. {
  34. outFile<<vec[i]<<endl;
  35. }
  36. return 0;
  37. }
  38.  
  39.  
  40.  
  41. void Quicksort(int vec[],int loBound,int hiBound )
  42. {
  43. int pivot;
  44. int loSwap;
  45. int hiSwap;
  46. int temp;
  47. if (loBound >= hiBound)
  48. return;
  49. if (hiBound-loBound == 1)
  50. {
  51. if (vec[loBound] > vec[hiBound])
  52. {
  53. temp = vec[loBound];
  54. vec[loBound] = vec[hiBound];
  55. vec[hiBound] = temp;
  56. }
  57. return;
  58. }
  59. pivot = vec[(loBound+hiBound)/2];
  60. vec[(loBound+hiBound)/2] = vec[loBound];
  61. vec[loBound] = pivot;
  62. loSwap = loBound + 1;
  63. hiSwap = hiBound;
  64. do {
  65. while (loSwap <= hiSwap && vec[loSwap] <= pivot)
  66. loSwap++;
  67. while (vec[hiSwap] > pivot)
  68. hiSwap--;
  69. if (loSwap < hiSwap)
  70. {
  71. temp = vec[loSwap];
  72. vec[loSwap] = vec[hiSwap];
  73. vec[hiSwap] = temp;
  74. }
  75. } while (loSwap < hiSwap);
  76. vec[loBound] = vec[hiSwap];
  77. vec[hiSwap] = pivot;
  78. Quicksort(vec, loBound, hiSwap-1);
  79. Quicksort(vec, hiSwap+1, hiBound);
  80. }
  81.